package com.eatme.core.search;

/**
 * 二分查找-非递归(修改循环不变量定义)
 */
public class BinarySearchV4 {
    private BinarySearchV4() {

    }

    // > target 的最小值索引
    public static <E extends Comparable<E>> int upper(E[] data,E target) {
        int l = 0, r = data.length;
        // 在data[l,r] 中寻找解
        while (l<r) {
            int mid = l+(r-l)/2;
            if (data[mid].compareTo(target) <= 0)
                l = mid+1;
            else
                r = mid;
        }
        return l;
    }

    // > target, 返回最小值索引
    // == target, 返回最大值索引
    public static <E extends Comparable<E>> int upper_ceil(E[] data,E target) {
        int u = upper(data,target);
        if (u-1>=0 && data[u-1].compareTo(target)==0)
            return u-1;
        return u;
    }

    // >= target, 返回最小值索引
    public static <E extends Comparable<E>> int lower_ceil(E[] data,E target) {
        int l = 0, r = data.length;
        // 在data[l,r] 中寻找解
        while (l<r) {
            int mid = l+(r-l)/2;
            if (data[mid].compareTo(target) < 0)
                l = mid+1;
            else
                r = mid;
        }
        return l;
    }

    // 使用求解 >= target 的最小值索引的思路，实现 search
    // 在有序数组 data 中判断 target 是否存在，存在则返回相应索引，不存在则返回 -1
    public static <E extends Comparable<E>> int search(E[] data,E target) {
        // 以下代码是求解 >= target 的最小值索引
        // ----------
        int l = 0, r = data.length;

        // 在 data[l, r] 中寻找解
        while(l < r){

            int mid = l + (r - l) / 2;
            if(data[mid].compareTo(target) < 0)
                l = mid + 1;
            else
                r = mid;
        }
        // ----------
        // 求解 >= target 的最小值索引算法结束
        // l 是 >= target 的最小值索引

        // 如果 data[l] == target，则返回 l；否则返回 -1
        // 注意，求解 >= target 的最小值索引，结果可能是 data.length，不是合法索引
        // 所以，我们要对 l 的合法性进行判断，即确定 l < data.length
        if(l < data.length && data[l].compareTo(target) == 0)
            return l;
        return -1;
    }



    // <= target 最大索引
    public static <E extends Comparable<E>> int upper_floor(E[] data,E target) {

        int l = -1, r = data.length - 1;

        // 在 data[l, r] 中寻找解
        while(l < r){
            int mid = l + (r - l + 1) / 2;
            // 请同学们根据下面的搜索范围的调整逻辑思考：
            // 为什么 upper_floor 同样需要使用上取整的方式来计算 mid?

            // 在 lower 中，这里是 data[mid].compareTo(target) < 0
            // 但是，对于 upper_floor 来说，在 data[mid] == target 的时候，有可能是解
            // 所以在等于的情况下，不能排除掉 data[mid] 的值，我们的搜索空间的变化，同样是 l = mid
            if(data[mid].compareTo(target) <= 0)
                l = mid;
            else
                r = mid - 1;
        }
        return l;
    }

    public static <E extends Comparable<E>> int lower(E[] data,E target) {
        int l = -1, r = data.length-1;
        // 在data[l,r] 中寻找解
        while (l<r) {
            int mid = l+(r-l+1)/2;
            if (data[mid].compareTo(target) < 0)
                l = mid;
            else
                r = mid-1;
        }
        return l;
    }

    // < target ，返回最大值索引
    // == target，返回最小索引
    public static <E extends Comparable<E>> int lower_floor(E[] data,E target) {
        int l = lower(data, target);
        // 注意，因为我们要访问 data[l + 1]，所以，我们要先确保 l + 1 不越界，
        // 即 l + 1 < data.length
        if(l + 1 < data.length && data[l + 1].compareTo(target) == 0)
            return l + 1;
        return l;
    }




    public static void main(String[] args) {
        Integer [] nums = {-1,0,3,5,9,12};
        Integer target = 9;
        int ret = BinarySearchV4.search(nums,target);
        System.out.println(ret);

        Integer[] arr = {1,1,3,3,5,5};
        for (int i = 0; i <= 6; i++)
            System.out.print(BinarySearchV4.upper(arr,i)+" ");
        System.out.println();

        for (int i = 0; i <= 6; i++)
            System.out.print(BinarySearchV4.upper_ceil(arr,i)+" ");
        System.out.println();

        for (int i = 0; i <= 6; i++)
            System.out.print(BinarySearchV4.lower(arr,i)+" ");
        System.out.println();

        System.out.print("lower_floor : ");
        for(int i = 0; i <= 6; i ++)
            System.out.print(BinarySearchV4.lower_floor(arr, i) + " ");
        System.out.println();

        System.out.print("upper_floor : ");
        for(int i = 0; i <= 6; i ++)
            System.out.print(BinarySearchV4.upper_floor(arr, i) + " ");
        System.out.println();

        System.out.print("lower_ceil : ");
        for(int i = 0; i <= 6; i ++)
            System.out.print(BinarySearchV4.lower_ceil(arr, i) + " ");
        System.out.println();



    }
}
